GATE IT 2004
Q21.
In a particular Unix OS, each data block is of size 1024 bytes, each node has 10 direct data block addresses and three additional addresses: one for single indirect block, one for double indirect block and one for triple indirect block. Also, each block can contain addresses for 128 blocks. Which one of the following is approximately the maximum size of a file in the file system?Q22.
An array of integers of size n can be converted into a heap by adjusting the heaps rooted at each internal node of the complete binary tree starting at the node \left \lfloor (n - 1) /2 \right \rfloor, and doing this adjustment up to the root node (root node is at index 0) in the order \left \lfloor (n - 1) /2 \right \rfloor,\left \lfloor (n - 3) /2 \right \rfloor, ....., 0. The time required to construct a heap in this manner isQ23.
What is the bit rate of a video terminal unit with 80 characters/line, 8 bits/character and horizontal sweep time of 100 \mu s (including 20 \mu s of retrace time)?Q24.
Let P be a singly linked list. Let Q be the pointer to an intermediate node x in the list. What is the worst-case time complexity of the best-known algorithm to delete the node x from the list ?Q25.
What is the minimum size of ROM required to store the complete truth table of an 8-bit \times 8-bit multiplier?Q26.
Consider the undirected graph below:Using Prim's algorithm to construct a minimum spanning tree starting with node A, which one of the following sequences of edges represents a possible order in which the edges would be added to construct the minimum spanning tree?Q27.
A relation Empdtl is defined with attributes empcode (unique), name, street, city, state and pincode. For any pincode, there is only one city and state. Also, for any given street, city and state, there is just one pincode. In normalization terms, Empdtl is a relation inQ28.
Consider the following entity relationship diagram (ERD), where two entities E1 and E2 have a relation R of cardinality 1:m.The attributes of E1 are A11, A12 and A13 where A11 is the key attribute. The attributes of E2 are A21, A22 and A23 where A21 is the key attribute and A23 is a multi-valued attribute. Relation R does not have any attribute. A relational database containing minimum number of tables with each table satisfying the requirements of the third normal form (3NF) is designed from the above ERD. The number of tables in the database isQ29.
A sender is employing public key cryptography to send a secret message to a receiver. Which one of the following statements is TRUE?Q30.
If we use internal data forwarding to speed up the performance of a CPU (R1, R2 and R3 are registers and M[100] is a memory reference), then the sequence of operations R1 \rightarrow M[100] M[100] \rightarrow R2 M[100] \rightarrow R3 can be replaced by